Graphs এবং Graph Traversal Techniques (BFS, DFS) গাইড ও নোট

গ্রাফ হলো একটি গাণিতিক কাঠামো যা ভেরটিস (vertices বা nodes) এবং তাদের মধ্যে সম্পর্ক নির্দেশকারী এজেস (edges) দিয়ে গঠিত। গ্রাফ বিভিন্ন ধরনের সম্পর্ক বা সংযোগ প্রদর্শন করতে ব্যবহৃত হয়, যেমন রাস্তা, নেটওয়ার্ক, সোসাল মিডিয়া সংযোগ ইত্যাদি। গ্রাফ প্রোগ্রামিং বা অ্যালগরিদম ডিজাইনে অত্যন্ত গুরুত্বপূর্ণ এবং এটি বিভিন্ন সমস্যা সমাধানে ব্যবহার করা হয়।

গ্রাফের মৌলিক উপাদান

১. ভেরটিস (Vertex বা Node):

• একটি গ্রাফের মৌলিক উপাদান, যা তথ্য বা অন্যান্য কোন বস্তু প্রতিনিধিত্ব করে।

২. এজ (Edge):

• দুটি ভেরটিসের মধ্যে সম্পর্ক বা সংযোগ। এজগুলি অভ্যন্তরীণ বা বাহ্যিক হতে পারে, অর্থাৎ এটি দিকনির্দেশিত (directed) বা দিকহীন (undirected) হতে পারে।

৩. ডিগ্রী (Degree):

• একটি ভেরটিসের সাথে যুক্ত এজের সংখ্যা। যদি গ্রাফটি দিকনির্দেশিত হয়, তবে এটি ইনডিগ্রী (incoming edges) এবং আউটডিগ্রী (outgoing edges) হিসেবে বিভক্ত হয়।

গ্রাফের ধরন

১. অবিচ্ছিন্ন গ্রাফ (Connected Graph):

• যেখানে একটি ভেরটিস থেকে অন্য যে কোনো ভেরটিসে পৌঁছানো সম্ভব।

২. অবিচ্ছিন্ন গ্রাফ (Disconnected Graph):

• যেখানে কিছু ভেরটিস অন্য ভেরটিস থেকে আলাদা, অর্থাৎ কিছু ভেরটিসে পৌঁছাতে অন্য ভেরটিসের মধ্য দিয়ে যাওয়া সম্ভব নয়।

৩. দিকনির্দেশিত গ্রাফ (Directed Graph):

• এখানে প্রতিটি এজ একটি দিক নির্দেশ করে। উদাহরণস্বরূপ, এক ভেরটিস থেকে অন্য ভেরটিসে যোগাযোগ।

4. দিকহীন গ্রাফ (Undirected Graph):
   • এখানে এজগুলির কোনো নির্দিষ্ট দিক নেই, অর্থাৎ একটি ভেরটিস থেকে অন্য ভেরটিসে যোগাযোগ দুই দিকেই হতে পারে।

গ্রাফ ট্র্যাভার্সাল টেকনিক্স

গ্রাফ ট্র্যাভার্সাল হল গ্রাফের প্রতিটি ভেরটিস পরিদর্শন করার প্রক্রিয়া। এই প্রক্রিয়ায় সাধারণত দুটি প্রধান ট্র্যাভার্সাল টেকনিক ব্যবহার করা হয়:

1. BFS (Breadth-First Search):

   • BFS হল একটি সারি (queue)-ভিত্তিক ট্র্যাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমটি প্রথমে গ্রাফের এক ভেরটিস (যে কোন একটি) থেকে শুরু করে তার সব সরাসরি প্রতিবেশী ভেরটিসগুলোকে পরিদর্শন করে, এবং তারপর প্রতিবেশীদের প্রতিবেশী, এবং এভাবে পরবর্তী স্তরের ভেরটিসগুলিকে পরিদর্শন করে। এটি স্তরভিত্তিক (level-order) ট্র্যাভার্সাল।

   BFS অ্যালগরিদমের পদক্ষেপ:

   1. প্রথমে, একটি ভিজিটেড (visited) অ্যারে বা সেট তৈরি করুন এবং গ্রাফের স্টার্টিং ভেরটিসটি ভিজিটেড হিসেবে চিহ্নিত করুন।
   2. একটি কিউতে স্টার্টিং ভেরটিসটি যুক্ত করুন।
   3. কিউ থেকে একটি ভেরটিস বের করুন, সেই ভেরটিসের সকল অজানা প্রতিবেশীকে কিউতে যুক্ত করুন এবং ভিজিটেড হিসেবে চিহ্নিত করুন।
   4. কিউ খালি না হওয়া পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।

   উদাহরণ (BFS):

   procedure BFS(graph: array of array of integer; start: integer);
   var
     queue: array[1..100] of integer;
     visited: array[1..100] of boolean;
     front, rear, i, v: integer;
   begin
     front := 1;
     rear := 1;
     visited[start] := True;
     queue[rear] := start;
     writeln('BFS Traversal: ');
     while front <= rear do
     begin
       v := queue[front];
       front := front + 1;
       write(v, ' ');
       for i := 1 to length(graph[v]) do
       begin
         if not visited[graph[v][i]] then
         begin
           visited[graph[v][i]] := True;
           rear := rear + 1;
           queue[rear] := graph[v][i];
         end;
       end;
     end;
     writeln;
   end;

2. DFS (Depth-First Search):

   • DFS হল একটি স্ট্যাক (stack)-ভিত্তিক ট্র্যাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমটি একটি ভেরটিস থেকে শুরু করে যতদূর সম্ভব গভীরভাবে (depth-first) যাবে এবং যখন আর গভীরে যাওয়া সম্ভব হবে না, তখন পিছিয়ে এসে পরবর্তী ভেরটিসের দিকে যাবে।

   DFS অ্যালগরিদমের পদক্ষেপ:

   1. একটি ভিজিটেড অ্যারে বা সেট তৈরি করুন এবং গ্রাফের স্টার্টিং ভেরটিসটি ভিজিটেড হিসেবে চিহ্নিত করুন।
   2. স্ট্যাক থেকে একটি ভেরটিস বের করুন, তার সকল অজানা প্রতিবেশীকে স্ট্যাকে যুক্ত করুন এবং ভিজিটেড হিসেবে চিহ্নিত করুন।
   3. স্ট্যাক খালি না হওয়া পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।

   উদাহরণ (DFS):

   procedure DFS(graph: array of array of integer; v: integer; visited: array of boolean);
   var
     i: integer;
   begin
     visited[v] := True;
     writeln(v);
     for i := 1 to length(graph[v]) do
     begin
       if not visited[graph[v][i]] then
         DFS(graph, graph[v][i], visited);
     end;
   end;

BFS এবং DFS এর মধ্যে পার্থক্য

সারাংশ

গ্রাফ এবং গ্রাফ ট্র্যাভার্সাল অ্যালগরিদমগুলি বিভিন্ন ধরনের সমস্যার সমাধানে গুরুত্বপূর্ণ। BFS (Breadth-First Search) স্তরভিত্তিক পরিদর্শন করে এবং প্রথমে নিকটবর্তী ভেরটিস পরিদর্শন করে, যা সরল এবং দ্রুত হয়। অন্যদিকে, DFS (Depth-First Search) গভীরতায় প্রবেশ করে এবং প্রথমে গভীরতম ভেরটিস পরিদর্শন করে। প্রতিটি অ্যালগরিদমের নিজস্ব সুবিধা এবং ব্যবহার রয়েছে, এবং নির্দিষ্ট সমস্যা অনুযায়ী এগুলোর নির্বাচন করা হয়।